package leet.ku._111;

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}

public class Solution {
	
	class Record {
		int depth;
		TreeNode node;
		Record(int d, TreeNode n) {
			depth = d;
			node = n;
		}
	}
	public int minDepth(TreeNode root) {
		if (root == null)
			return 0;
		Queue<Record> queue = new LinkedList<Record>();
		queue.add(new Record(1, root));
		while (!queue.isEmpty()) {
			Record now = queue.poll();
			if (now.node.left == null && now.node.right == null)
				return now.depth;
			if (now.node.left != null)
				queue.add(new Record(now.depth + 1, now.node.left));
			if (now.node.right != null)
				queue.add(new Record(now.depth + 1, now.node.right));
		}
		return -1;
	}
}